package Z.dailyExercise._0109;

public class _69_x的平方根 {
    public static void main(String[] args) {
        _69_x的平方根 test = new _69_x的平方根();
        System.out.println(test.mySqrt(2147395600));
    }

    /**
     * 自解：二分查找 如果小的 mid+1
     * ======大整形的时候 要讲搜索范围调整成长整型 因此用long
     * @param x
     * @return
     */
    public int mySqrt(int x) {

        if (x<=1){
            return x;
        }

        return find(x,0,x-1);
    }

    public int find(int x,int low,int high){

        if (low == high){
            return low+1;
        }

        long mid = (low+high)/2;
        long num = mid+1;

        if (num*num > x){
            return find(x,low,(int) mid);
        }else if (num*num == x){
            return (int) num;
        }else {//其他处理：如果小的话 递归mid+1
            while (num * num <= x){
                num ++;
            }

            return (int)num-1;

        }

    }
}
